package com.zhupf.part7;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhupf
 * @date 2023年11月23日 14:24
 * @Description
 * 146、LEU缓存
 */
public class LRUCache {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(2,1);
        lruCache.put(1,1);
        lruCache.put(2,3);
        lruCache.put(4,1);
        lruCache.get(1);
        lruCache.get(2);
    }


    private ListNode head = new ListNode(0);

    private ListNode tail = new ListNode(0);

    private Map<Integer, ListNode> cache;

    private int capacity;

    private int curSize;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        ListNode listNode = cache.get(key);
        if (listNode == null) {
            return -1;
        }
        listNode.pre.next = listNode.next;
        listNode.next.pre = listNode.pre;
        listNode.next = head.next;
        head.next.pre = listNode;
        head.next = listNode;
        listNode.pre = head;
        return listNode.val;
    }

    public void put(int key, int value) {
        ListNode listNode = cache.get(key);
        if (listNode != null) {
            listNode.val = value;
            listNode.pre.next = listNode.next;
            listNode.next.pre = listNode.pre;
        } else {
            listNode = new ListNode(key, value);
            cache.put(key, listNode);
            curSize++;
        }
        listNode.next = head.next;
        head.next.pre = listNode;
        head.next = listNode;
        listNode.pre = head;
        if (curSize > capacity) {
            cache.remove(tail.pre.key);
            tail.pre = tail.pre.pre;
            tail.pre.next = tail;
            curSize--;
        }
    }

    static class ListNode {

        private int key;

        private int val;

        private ListNode next;

        private ListNode pre;

        public ListNode() {
        }

        public ListNode(int key) {
            this.key = key;
        }

        private ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }

    }
}
